from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def isValid(self, s):
        stack = []
        for c in s:
            if c in '([{':
                stack.append(c)
            elif stack and self.leftOf(c) == stack[-1]:
                stack.pop()
            else:
                return False
        return not stack

    def leftOf(self, c):
        if c == '}':
            return '{'
        if c == ')':
            return '('
        return '['
# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    # your test code here